#coding=utf-8

#股票买卖
def max_profit_dc(prices:list)->int:
    len_prices = len(prices)
    if len_prices <= 1:
        return 0
    mid = len_prices // 2
    prices_left = prices[:mid]
    prices_right = prices[mid:]
    maxprofit_left = max_profit_dc(prices_left)
    maxprofit_right = max_profit_dc(prices_right)
    maxprofit_left_right = max(prices_right) - min(prices_left)
    return max(maxprofit_left,maxprofit_right,maxprofit_left_right)

# print(max_profit_dc([13,17,15,8,14,15,19,7,8,9]))

#统计逆序
def count_inversions_dc(A:list):
    lenA = len(A)
    if lenA <= 1:
        return 0,A
    middle = lenA // 2
    leftA = A[:middle]
    rightA = A[middle:]
    countLA , leftA = count_inversions_dc(leftA)
    countRA , rightA = count_inversions_dc(rightA)
    countLRA , mergedA = merge_and_count(leftA,rightA)

    return countLA+countRA+countLRA,mergedA

def merge_and_count(A,B):
    i,j,inv_count = 0,0,0
    alist = []
    lenA = len(A)
    lenB = len(B)
    while i<lenA and j<lenB:
        if A[i] < B[j]:
            alist.append(A[i])
            i+=1
        else:
            inv_count += lenA-i
            alist.append(B[j])
            j+=1
    while i<lenA:
        alist.append(A[i])
        i+=1
    while j<lenB:
        alist.append(B[j])
        j+=1
    return inv_count,alist

# print(count_inversions_dc([2, 4, 1, 3, 5]))

#最大连续和
def findMaxSum_Onlogn(A):
    if len(A) <= 1:
        return A[0]
    mid = len(A) // 2
    leftA = A[:mid]
    rightA = A[mid:]
    leftMaxSum = findMaxSum_Onlogn(leftA)
    leftAfinal = 0
    leftAfinalMax = -float('Inf')
    for i in range(0, len(leftA))[::-1]:
        leftAfinal = leftAfinal + leftA[i]
        if leftAfinal > leftAfinalMax:
            leftAfinalMax = leftAfinal
    rightMaxSum = findMaxSum_Onlogn(rightA)
    rightAfinal = 0
    rightAfinalMax = -float('Inf')
    for j in range(0, len(rightA)):
        rightAfinal = rightAfinal + rightA[j]
        if rightAfinal > rightAfinalMax:
            rightAfinalMax = rightAfinal
    crossMaxSum = leftAfinalMax + rightAfinalMax
    return max(leftMaxSum, rightMaxSum, crossMaxSum)
